public class Partition {
    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    //    现有一链表的头指针 ListNode* pHead，给一定值x，
//    编写一段代码将所有小于x的结点排在其余结点之前，
//    且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        ListNode cura1 = null;
        ListNode curb1 = null;
        ListNode cura2 = null;
        ListNode curb2 = null;
        ListNode cur = head;
        while (cur != null) {
            if (x > cur.val) {
                if (cura1 == null) {
                    cura1 = cur;
                    curb1 = cur;
                } else {
                    curb1.next = cur;
                    curb1 = curb1.next;
                }
            } else {
                if (cura2 == null) {
                    cura2 = cur;
                    curb2 = cur;
                } else {
                    curb2.next = cur;
                    curb2 = curb2.next;
                }
            }
            cur = cur.next;
        }
        if (cura1 == null) {
            return cura2;
        }
        curb1.next = cura2;
        if (curb2 != null) {
            curb2.next = null;
        }
        return cura1;
    }

    //    给你两个单链表的头节点 headA 和 headB ，
//    请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    public ListNode getIntersectionNode(ListNode head1, ListNode head2) {
        if (head1==null||head2==null){
            return null;
        }
        int size1=size(head1);
        int size2=size(head2);
        int size=size1-size2;
        //设长链表为head1，短链表为head2
        if(size<0){
            size=-1*size;
            ListNode tmp=head1;
            head1=head2;
            head2=tmp;
        }
        while(size>0){
            size--;
            head1=head1.next;
        }
        while(head1!=head2){
            head1=head1.next;
            head2=head2.next;
        }
    return head1;
    }
    public int size(ListNode head){
        int count=0;
        while(head!=null){
            count++;
            head=head.next;
        }
        return count;
    }
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow) {
                    return true;
                }
            }
            return false;
    }

    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;
        }
        slow=head;
        while (slow!=fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
